The present invention relates to computer networks and, more particularly, to use of a routing information field of a token ring frame to increase the efficiency of intermediate devices of a computer network.
Data communications in a computer network involves the exchange of data between two or more entities interconnected by communication links and subnetworks. These networks are typically software programs executing on hardware computer platforms which, depending on their roles within a network, may serve as end stations or intermediate stations. Examples of intermediate stations include routers, bridges and switches that interconnect communication links in subnetworks; an end station may be a computer located on one of the subnetworks. More generally, an end station connotes a source of or target for data that typically does not provide routing or other services to other computers on the network. A local area network (LAN) is an example of a subnetwork that provides relatively short-distance communication among the interconnected stations; in contrast, a wide area network (WAN) facilitates long-distance communication over links provided by public or private telecommunications facilities.
End stations typically communicate by exchanging discrete packets or frames of data according to pre-defined protocols. In this context, a protocol represents a set of rules defining how the stations interact with each other to transfer data. Such interaction is simple within a LAN, since these are typically xe2x80x9cmulticastxe2x80x9d networks: when a source station transmits a frame over the LAN, it reaches all stations on that LAN. If the intended recipient of the frame is connected to another LAN, the frame is passed over a routing device to that other LAN. Collectively, these hardware and software components comprise a communications network and their interconnections are defined by an underlying architecture.
Most computer network architectures are organized as a series of hardware and software levels or xe2x80x9clayersxe2x80x9d within each station. These layers interact to format data for transfer between, e.g., a source station and a destination station communicating over the network. Specifically, predetermined services are performed on that data as it passes through each layer, and the layers communicate with each other by means of the predefined protocols. This design permits each layer to offer selected services to other layers using a standardized interface that shields the other layers from details of actual implementation of the services. The lower layers of these architectures are generally standardized and implemented in hardware and firmware, whereas the higher layers are usually implemented in the form of software. Examples of such communications architectures include the System Network Architecture (SNA) developed by International Business Machines (IBM) Corporation and the Internet Communications Architecture.
The Internet architecture is represented by four layers termed, in ascending interfacing order, the network interface, internetwork, transport and application layers. The primary internetwork layer protocol of the Internet architecture is the Internet Protocol (IP). IP is primarily a connectionless protocol that provides for internetworking routing, fragmentation and reassembly of exchanged packetsxe2x80x94generally referred to as xe2x80x9cdatagramsxe2x80x9d in an Internet environmentxe2x80x94and which relies on transport protocols for end-to-end reliability. An example of such a transport protocol is the Transmission Control Protocol (TCP), which is implemented by the transport layer and provides connection-oriented services to the upper layer protocols of the Internet architecture. The term TCP/IP is commonly used to denote this architecture; the TCP/IP architecture is discussed in Computer Networks, 3rd edition, by Andrew S. Tanenbaum, published by Prentice-Hall, PTR in 1996, all disclosures of which are incorporated herein by reference, particularly at pages 28-44.
SNA is a communications framework widely used to define network functions and establish standards for enabling different models of computers to exchange and process data. SNA is essentially a design philosophy that separates network communications into several layers termed, in ascending order, the physical control, the data link control, the path control, the transmission control, the data flow control, the presentation services and the transaction services layers. Each of these layers represents a graduated level of function moving upward from physical connections to application software.
In the SNA architecture, the data link control layer is responsible for transmission of data from one end station to another. Bridges or devices in the data link control layer are used to connect two or more LANs so that end stations on either LAN are allowed to access resources on the LANs. Connection-oriented services at the data link layer generally involve three distinct phases: connection establishment, data transfer and connection termination. During connection establishment, a single path or connection, e.g., an IEEE 802.2 logical link control type 2 (LLC2) connection, is established between the source and destination stations. Once the connection has been established, data is transferred sequentially over the path and, when the LLC2 connection is no longer needed, the path is terminated. Reliable communication in the data link layer is well known and described by Andrew Tanenbaum in his book Computer Networks, Second Edition, published in 1988, all disclosures of which are incorporated herein by reference, especially at pages 253-257.
FIG. 1 is a schematic block diagram of a conventional computer network 100 having a source end station (Host A) coupled to a Token Ring (TR) network TR1 and a destination end station (Host B) coupled to TR2. The TR networks are of a type that support Source Route Bridging (SRB) operations with respect to the contents of a routing information field (RIF) of a frame. A SRB bridge B1 interconnects TR1 and TR2 such that the SRB network 100 effectively functions as a LAN. Host A communicates with Host B by exchanging TR frames over LLC2 connections or sessions through the SRB network 100. To send a TR frame from Host A to Host B along a particular path of the network, the source may insert information within the RIF of the frame that specifies the particular path to the destination.
FIG. 2 is a schematic diagram of a portion of a conventional TR frame 200 comprising destination address (DA) and source address (SA) medium access control (MAC) fields 202-204 and a RIF header 210. The RIF header 210, in turn, comprises a type (TYPE) field 212, a RIF length indicator (LENGTH) field 214, a direction bit (DIRECTION) field 216 and a ROUTE field 220 that may include a plurality of ring number (RN)/bridge number (BN) pairs or route descriptor (RD) xe2x80x9chopsxe2x80x9d needed to describe the path. Each RD comprises 2 bytes, wherein the RN is 12 bits and the BN is 4 bits. For example, the ROUTE field 220 of TR frame 200 transmitted by Host A to Host B may contain [0011.0020]. The RIF header 210 terminates with a 4-bit padding (PAD) field 228 of zeros.
The bridged TR network 100 is typically implemented through the use of TR concentrators (or xe2x80x9chubsxe2x80x9d) interconnected in a xe2x80x9cdaisy chainxe2x80x9d manner, wherein each concentrator is coupled to end stations via point-to-point wires. Access to each token ring of network 100 is determined in accordance with a token message that propagates among all of the end stations coupled to the ring. A concern with this conventional network arrangement involves the limited bandwidth available to each station over the wires; for example, all end stations coupled to a physical token ring share 16 megabits (Mbps) of bandwidth.
An attempt to increase bandwidth in a token ring environment involves the use of intermediate stations that are compatible with the Dedicated Token Ring (DTR) bridge standard promulgated by the Institute of Electrical and Electronic Engineers (IEEE) in Annex K to the IEEE 802.5 standard (hereinafter xe2x80x9cAnnex Kxe2x80x9d), which governs token ring LANS. Annex K defines a two-tier switching model for a single LAN switch containing a Bridge Relay Function (BRF) to bridge between ports of different ring numbers and a Concentrator Relay Function (CRF) to switch between ports of the same ring number.
FIG. 3 is a highly schematic diagram of a switch 300 containing a plurality of CRFs (CRF 111-333) coupled to a BRF1 to provide bridging and switching operations among physical TR media/segments coupled to the switch. Each CRF has a plurality of ports that interconnect a plurality of TR segments into one logical token ring having a single ring number. This arrangement is advantageous because it increases the total available bandwidth per logical token ring. That is for a 4-port switch arrangement, a total of 64 Mbps of bandwidth is available for, .e.g., CRF 111.
Functionally, the CRF xe2x80x9cswitchesxe2x80x9d TR frames from one TR segment to another, while the BRF xe2x80x9cbridgesxe2x80x9d those frames between those different CRFs. That is rather than or in addition to forwarding frames from one TR segment to another, CRF111 may pass them to its associated BRF1 which may, in turn, forward the frames to CRF222. CRF222 may then forward the frames over one of its TR segments. In the case of a TR frame having a RIF, the switch decides where to forward the frame based on the contents of its RIF. To that end, interface circuitry of each port scans the RIF looking for its matching RD and, upon upon finding it, interprets the contents of the RIF following the matching RD in order to render a forwarding decision for the frame. Rendering of forwarding decisions for frames by interpreting the contents of their RIFs may be time consuming and generally inefficient. The present invention is directed, in part, to a technique for improving the efficiency of rendering such forwarding decisions.
A LLC2 session is established between the end stations using a special TR frame, called an explorer frame. Referring again to FIG. 1, the explorer frame is used by a source (Host A) to xe2x80x9cdiscoverxe2x80x9d the path to a destination (Host B); thereafter, a Set Asynchronous Balanced Mode Extended (SABME) frame is sent from Host A to Host B to establish a logical connection between the end stations, and Host B responds to the SABME frame with an Unnumbered Acknowledgment (UA) frame. Once the UA frame is received by Host A, a connection is established between the source and destination, and these end stations communicate by exchanging TR information (INFO) and acknowledgment frames until the logical link session is completed.
For example, Host A transmits an INFO frame over TR1 and through BR1 and TR2 to Host B. Upon successfully receiving the INFO frame, Host B responds by transmitting an LLC2 Receive/Ready (RR) acknowledgment frame over the SRB network to Host A. This INFO/RR exchange continues until Host A has successfully transmitted all of its data and Host B has successfully received all of that data. Session completion is then initiated by a Disconnected Mode (DM) frame being transmitted from Host A to Host B; the disconnection is thereafter acknowledged by Host B responding with a UA frame. The LLC2 frames (packets) are described by Radia Perlman in her book Interconnections, Bridges and Routers, published by Addison Wellesly Publishing Company, in 1992, all disclosures in which are incorporated here in by reference, particularly at pages 33-34.
As noted, each TR INFO frame sent from a source to a destination is acknowledged by an RR frame; if the source end station does not receive the acknowledgment frame within a prescribed period of time, a xe2x80x9ctime-outxe2x80x9d may occur and the source sends a DM frame to prematurely terminate the session. Since network 100 is a LAN, it facilitates fast transfer of information between its connected stations and, as a result, a time-out condition should rarely occur. If a WAN such as a TCP/IP cloud is disposed within a LAN-based network, it is likely that a time-out will arise because of the latencies introduced by the TCP/IP cloud. That is, a frame traversing the WAN cloud incurs substantial delay as opposed to the LAN because the WAN is generally not as fast as the LAN.
Data Link Switching (DLSw) is a mechanism for forwarding SNA and Network Basic Input/Output Services (NetBios) protocol frames over a TCP/IP backbone WAN such as the Internet. In traditional bridging, the data link connection is end-to-end, i.e., effectively continuous between communicating end stations. A stream of data frames originating from a source end station on a source LAN traverses one or more bridges specified in the path over the LLC2 connection to a destination station on a destination LAN. In a network implementing DLSw, by contrast, the LLC2 connection terminates at a local DLSw device, e.g., a switch. An example of a DLSw network arrangement may comprise a local DLSw device connected to a local LAN having a source end station and a remote DLSw device connected to a remote LAN having a destination end station. The LANs that are accessed through the DLSw devices may appear as SRB subnetworks attached to adjacent rings; each of these adjacent rings manifests as a virtual ring within each DLSw device that effectively terminates the SRB network.
FIG. 4 is a schematic block diagram of such a DLSw network 400 having a TCP/IP cloud 410 disposed between local and remote SRB subnetworks 402, 404. When communicating with Host B as described above, Host A sends an INFO frame to which Host B responds with an acknowledgement, such as a RR frame. Because of the latencies introduced by the WAN cloud, however, a time-out condition may occur during this exchange. To address this issue, the DLSw network includes local and remote DLSw devices 1,2 that border the WAN cloud. These DLSw devices function as end points between TCP sessions over the TCP/IP cloud when transporting TR frames associated with LLC2 sessions over that intermediate network. DLSw switching may obviate the timeout issue introduced by the TCP/IP cloud by, e.g., having DLSw1 return a RR acknowledgment frame to the source end station (Host A) upon receiving an INFO frame. Notably, the RR frame is returned prior to transmitting the native TR INFO frame over the TCP/IP network.
Broadly stated, each DLSw device establishes a xe2x80x9cpeer relationshipxe2x80x9d to the other DLSw device in accordance with a conventional capabilities exchange message sequence, and the logical and physical connections between these devices connect the subnetworks into a larger DLSw network. To establish a DLSw peer connection, the local DLSw device first opens logical TCP (Read/Write) xe2x80x9cpipexe2x80x9d connections to the remote DLSw device using a conventional socket technique to create a socket into the transport layer of the protocol stack. Once the TCP pipes are established, a switch-to-switch protocol (SSP) is used to transport the capabilities exchange messages between the two DLSw devices.
The capability exchange messages contain various parameters, such as the number of pipes used for communicating between the DLSw devices and the largest frame size supported by the devices. Each DLSw device responds to each capability exchange message issued by its peer device with a capability exchange response message. Upon completion of the exchange, each device reconfigures itself to xe2x80x9cact uponxe2x80x9d the agreed capabilities and the peer connection is established. Establishment of a peer connection can occur automatically upon xe2x80x9cboot-upxe2x80x9d of each DLSW device; that is, as soon as a DLSw device activates, it connects with its DLSw peer. The DLSw forwarding mechanism is well known and described in detail in Wells et al. Request For Comment (RFC) 1795 (1995).
Upon receiving a TR frame from a source on the local SRB network, the local DLSw device employs the SSP protocol to communicate with its DLSw peer device by forwarding the native TR frame over the TCP/IP network to the remote SRB subnetwork.
That is, the TR frame received at the local DLSw switch from the source is encapsulated within a SSP protocol frame and forwarded over the TCP/IP cloud to the remote DLSw switch. The source route information contained in the RIF of each TR frame terminates inside the virtual ring of the DLSw switch; the RIF information is locally stored at the DLSw switch.
The local DLSw device then multiplexes the LLC2 data stream over a conventional TCP transport connection to a remote DLSw device. LLC2 acknowledgment frames used to acknowledge ordered receipt of the LLC2 data frames are xe2x80x9cstripped-outxe2x80x9d of the data stream and acted upon by the local DLSw device; in this way, the actual data frames are permitted to traverse the IP cloud to their destination while the xe2x80x9coverheadxe2x80x9d acknowledgment frames required by the LLC2 connections for reliable data delivery are kept off the cloud. The LLC2 connections from the source LAN to the local transmitting DLSw device, and from the remote receiving DLSw device to the destination LAN, are entirely independent from one another. Data link switching may be further implemented on multi-protocol routers capable of handing DLSw devices as well as conventional (e.g., SRB) frames.
DLSw devices can establish multiple parallel TCP sessions using well-known port numbers. All frames associated with a particular LLC2 connection typically follow a single designated TCP session. For example, SNA data frames originating at Host A are transmitted over a particular LLC2 connection along TR1 to DLSw1, where they are encapsulated within a designated TCP session as packets and transported over the TCP/IP cloud 410. The encapsulated messages are received by DLSw2, decapsulated to their original frames and transmitted over a corresponding LLC2 connection of TR2 to Host B in the order received by DLSw1 from Host A.
The LLC2 connection between Host A and Host B is identified by a data link identifier (ID) 460 consisting of a pair of attachment addresses associated with each end station. Each attachment address is represented by the concatenation of a media access control (MAC) address (6 bytes) and a LLC service access point (SAP) address (1 byte). Specifically, each attachment address is classified as either a target address comprising destination MAC (DMAC) and destination SAP (DSAP) address, or an origin address comprising source MAC (SMAC) and source SAP (SSAP) addresses. The attachment addresses are contained in the TR frames exchanged between the Host A and Host B stations.
Furthermore, the designated TCP session is identified by a pair of circuit IDs 470, each comprising a 64-bit number that identifies the LLC2 circuit within a DLSw circuit. The DLSw circuit ID generally comprises a data link circuit port ID (4 bytes) and a data link correlator (4 bytes). A pair of circuit IDs along with a data link ID uniquely identify a single end-to-end circuit through the network. Notably, each DLSw router maintains a table 450 comprising a plurality of data link ID and corresponding DLSw circuit ID pair entries. In order to associate LLC2 frame traffic with a corresponding DLSw circuit when communicating over the IP cloud, each DLSw device typically searches the table (the xe2x80x9cDLSw tablexe2x80x9d) using a data link ID to find the corresponding DLSw circuit IDs. For a typical DLSw implementation having a plurality of TCP sessions between DLSw peer devices, searching of a DLSw table by data link ID may be time consuming and generally inefficient. The present invention is directed, in part, to providing an efficient searching technique.
Typically, all packets transmitted by a DLSw device over a LLC2 connection/TCP session flow at the same priority level from a single output queue of the transmitting DLSw peer device and arrive at an input queue of the receiving DLSw peer device in the same order in which they are transmitted. However, it may be desired to prioritize the packets in an order governed by specified transmission priority information levels. The present invention is further directed to providing an efficient means for prioritizing packets transmitted by a DLSw switch over a DLSw network.
The present invention comprises a technique for increasing the efficiency of functions performed by an intermediate device of a computer network by encoding a predetermined portion of a routing information field (RIF) of a token ring (TR) frame transported over the network with information for use by the device. According to the technique, the maximum number of route descriptor (RD) network xe2x80x9chopsxe2x80x9d stored in the RIF is altered to provide the predetermined portion of the RIF for storing encoded information. Each intermediate device configured in accordance with the inventive technique identifies this predetermined portion as that portion of the RIF immediately following its matching RD.
In one aspect of the invention, the intermediate device is a Data Link. Switching (DLSw) switch configured to encode a first predetermined portion of the RIF with a value that enables efficient searching of a DLSw table. The value is preferably a session index used to access information stored on the DLSw table when correlating logical link control type 2 frames with switch-to-switch protocol frames transmitted over transmission control protocol (TCP) connection sessions through a TCP/IP cloud of the network. Encoding of the RIF with a session index increases the efficiency of table searching since a relatively small value, instead of a larger address, is used to access the table.
In another aspect of the present invention, the technique may further comprise encoding a second predetermined portion of the RIF to provide prioritization information associated with TR frames transmitted over the TCP sessions. Typically, frames transmitted by a DLSw device over a TCP session flow at the same priority level from a single output queue of a device and arrive at a DLSw peer device in the same order in which they are transmitted. However, the present invention provides a means for prioritizing the frames in an order specified by transmission priority information available at the DLSw device.
In yet another aspect of the present invention, the intermediate device may be configured as a TR switch having a plurality of Concentrator Relay Functions (CRF) coupled to a Bridge Relay Function (BRF). The TR switch may encode a predetermined portion of the RIF with information that enables efficient rendering of forwarding decision operations with respect to subsequent frames received at and transmitted from ports associated with the CRFs. Here, port circuitry at each inbound port of the switch scans the RIF looking for its matching RD. Upon finding the matching RD, the port circuitry encodes the predetermined portion of the RIF with an identifier that enables quick access to entries of a forwarding table when rendering forwarding decisions for the subsequent frames.
Advantageously, the inventive technique allows a switch to utilize a portion of the RIF for encoding any type of information for use in the network. Encoding of such information increases the performance of bridging applications executed on the switch. Moreover, session switching using an encoded portion of the RIF increases the performance of the switch since table xe2x80x9clook-upxe2x80x9d operations are based on a small value (i.e., an index or identifier) rather rather than a larger address.